package com.xy6.algo.dynamic;


/**
 * 01背包问题
 * <pre>
 * 法一：性价比方法
 * 法二：动态规划
 * 求解该问题，关键在于考虑到第i件物品是否放入背包。
 * 放，先为物品i腾出空间，计算最大价值，再加物品i的价值；
 * 不放，前i-1个物品的最大价值；
 * 
 * 状态转移方程：
 * 假设：i表示前i件物品，j表示背包承重，v[i]表示物品i的价值，w[i]表示物品i的重量
 * f(i,j) = max(f(i-1, j-w[i]) + v[i], f[i-1, j])
 * i为1-n（物品个数），j为1-W（背包最大承重）
 * </pre>
 * 
 * @author zhang
 * @since 2017-10-23
 */
public class Package {

	public static void main(String[] args) {
		int v[] = { 0, 10, 25, 40, 20, 10 };
		int w[] = { 0, 40, 50, 70, 40, 20 };
		int total = 120;
		System.out.println(calc(v, w, total));

		v = new int[] { 2, 3, 4, 5, 6 };
		w = new int[] { 1, 2, 3, 4, 5 };
		total = 10;
		System.out.println(calc(v, w, total));
	}

	/**
	 * 求解01背包问题
	 * <pre>
	 * 性价比方法
	 * </pre>
	 * 
	 * @param v 各物品价值
	 * @param w 各物品重量
	 * @param total 背包承受重量
	 */
	public static int calc(int[] v, int[] w, int total) {
		int n = v.length;
		double price[] = new double[n];
		int product[] = new int[n];
		// 计算每个物品性价比
		for (int i = 0; i < v.length; i++) {
			price[i] = v[i] * 1.0 / w[i] * 1.0;
			product[i] = i;
		}
		// 按性价比倒序排列。可使用快排等替换，提高性能
		double tempPrice = 0;
		int tempProduct = 0;
		for (int i = 0; i < n; i++) {
			for (int j = i; j < n; j++) {
				if (price[i] < price[j]) {
					tempPrice = price[i];
					price[i] = price[j];
					price[j] = tempPrice;
					tempProduct = product[i];
					product[i] = product[j];
					product[j] = tempProduct;
				}
			}
		}
		// 逐个物品放入背包
		int putW = 0;
		int putV = 0;
		for (int i = 0; i < n; i++) {
			int prod = product[i];
			if (v[prod] > 0 && w[prod] + putW <= total) {
				putW += w[prod];
				putV += v[prod];
			}
		}
		
		return putV;
	}

	/**
	 * 动态规划求解01背包问题
	 * 
	 * @param v
	 * @param w
	 * @param total
	 */
	public static int calcByDP(int[] v, int[] w, int total) {
		// 背包承重为i，前j个物品，最大价值
		int[][] f = new int[total+1][v.length];
		int temp1 = 0;
		for (int i = 1; i <= total; i++) {
			for (int j = 0; j < w.length; j++) {
				// 放入物品j，不放物品j，取最大值
				temp1 = 0;
				if(i >= w[j]){
					temp1 = f(f, i - w[j], j - 1) + v[j];
				}
				f[i][j] = max(temp1, f(f, i, j - 1));
			}
		}
		
		// 最后一个元素为最大值
		return f[total][w.length - 1];
	}
	
	/**
	 * 获取指定下标的元素，并判断下标有效性
	 * 
	 * @param f
	 * @param w
	 * @param n
	 * @return
	 */
	private static int f(int[][] f, int i, int j){
		if(i < 0 || j < 0 || i > f.length || j > f[0].length){
			return 0;
		}
		return f[i][j];
	}
	
	/**
	 * 计算两个数最大值
	 * 
	 * @param i
	 * @param j
	 * @return
	 */
	private static int max(int i, int j){
		return i > j ? i : j;
	}
	
}
